This invention relates to determining a bounding shape for a collection of points.
One way to accelerate the drawing of graphics is to avoid processing objects that are not visible in a frame, e.g., objects that are xe2x80x9coff camera.xe2x80x9d One way to avoid processing off camera objects is to calculate a bounding shape that encompasses all of the points on a given object and then to use the bounding shape to test whether to exclude the entire object from processing. In a multi-dimensional graphics system, e.g., three-dimensional (xe2x80x9c3-Dxe2x80x9d), the collection of points, e.g., (x,y,z) coordinates, on an object in a frame is the vertex pool for each object""s bounding shape.
Bounding shapes can be useful in a variety of processing scenarios. For scene management, off camera objects may not need updating in every new frame. For example, a wheel of a car may be off camera in a particular frame. Processing the car but not the hidden (off camera) wheel decreases the amount of time and computation that would be necessary if the wheel were processed and then later discarded before the frame is finally rendered. An object such as the wheel will be off camera if its bounding shape is off camera. The test to determine if the bounding shape is off camera is much simpler than the test to determine if all points of the object are off camera.
For run-time animation, intersections of objects may need to be determined. For example, part of a wheel of a car may be obscured by a rock in the road. Refraining from processing the off camera portions of the wheel decreases the amount of time and computation that would be necessary if the entire wheel were processed and later partially obscured by the rock. If the bounding shapes of two objects such as the wheel and the rock do not intersect, then the objects do not intersect. Testing for the intersection of two bounding shapes is much simpler than testing for the intersection of two complicated objects.
In ray tracing rendering methods, the intersection of a ray with an object needs to be determined. A quick test to determine if the ray intersects a bounding shape of the object can be used to avoid work if there is no intersection. Any intersection points may give an initial range for some ray tracing methods.
One known method of calculating bounding spheres is described in Jack Ritter, xe2x80x9cAn Efficient Bounding Sphere,xe2x80x9d in GRAPHICS GEMS, Andrew S. Glassner (ed.), Academic Press, Inc., Boston, 1990, pp. 301-03, 723-25. As shown in FIG. 1, the Ritter method finds the location and size of a bounding circle 10, e.g., a 3-D sphere, for a collection of points 12 by the following steps. First, the method finds the points that have the minimum and maximum positions along each dimension, points 14a and 14b (x dimension) and 16a and 16b (y dimension). The method then finds the dimension that has the largest distance between its minimum and maximum points 14 or 16. Here it is the y dimension between points 16a and 16b. The method next calculates an initial radius 18 of an initial bounding sphere 20 as one half the distance between the minimum and maximum points 16a and 16b. The method also calculates an initial center 22 of the initial bounding sphere 20 as the average of the minimum and maximum points 16a and 16b. 
Now, to see if the initial bounding sphere 20 encloses all points in the collection 12, the method checks each point in the collection 12 to see if the distance between it and the initial center 22 is greater than the initial radius 18. For the first point in the collection 12 that is outside the initial sphere 20, the initial radius 18 and initial center 22 change to an intermediate radius 24 and an intermediate center 26 to define an intermediate bounding sphere 28. All subsequent points are evaluated using the intermediate values 24 and 26, which can change in the same way as the initial values 18 and 22. Checking all of the points in the collection in this manner requires a number of calculations. The more points in the collection 12, the higher the number of required calculations. Once all points in the collection 12 have been checked against the appropriate sphere 20 or 28, the final bounding sphere 10 is defined by the appropriate radius 18 or 24 and center 22 or 26.
In general, in one aspect, the invention features determining a multi-dimensional bounding sphere for a collection of points by determining a multi-dimensional bounding box that encompasses all of the points, determining the center of the bounding sphere from the center of the bounding box, and determining the radius of the bounding sphere as the distance from the center of the bounding sphere to a location not closer to the center of the bounding sphere than any of the points in the collection of points.
In another aspect, the invention features an apparatus for determining a three-dimensional bounding sphere for a collection of points including a storage unit to store the collection of points and a processor. The processor is configured to determine a three-dimensional bounding box that encompasses all of the points, to determine the center of the bounding sphere from the center of the bounding box, and to determine the radius of the bounding sphere as the distance from the center of the bounding sphere to a location not closer to the center of the bounding sphere than any of the points in the collection of points.
In another aspect, the invention features determining a bounding sphere for a collection of points by determining a bounding box that encompasses all of the points, determining a center of the bounding box, determining the one of the points that is farthest away from the center, and determining a radius of the bounding sphere as the distance from the center to the one of the points that is farthest away from the center.
In another aspect, the invention features determining a bounding sphere for a collection of points by determining a bounding box that encompasses all of the points, determining a center of the bounding box, and determining a radius of the bounding sphere as the distance from the center to a corner of the bounding box.
Other advantages and features will become apparent from the following description and from the claims.